package com.example.demo.LeetCode.list.fastSlow;

import com.example.demo.LeetCode.list.ListNode;

/**
 * 快满指针解决
 * 查找链表中间节点
 */
public class MiddleNode {
    /**
     * 慢指针slow前进一步，快指针前进两步
     * 当fast走到链表末尾，slow就指向链表中点
     * @param head
     * @return
     */
    public static ListNode middleNode(ListNode head) {
        //快慢指针初始化指向head
        ListNode slow = head,fast = head;
        //快慢指针走到末尾时停止
        while(fast != null && fast.next != null){
          //慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
        }
        //慢指针指向中点
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode p1 = new ListNode(2);
        ListNode p2 = new ListNode(3);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(4);
        head.next = p1;
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        ListNode res = middleNode(head);
        while(res!=null){
            System.out.print(res.val + ", ");
            res = res.next;
        }
    }
}
